#include <bits/stdc++.h>

using namespace std;

// 数位 DP 上下界模板
// 给你三个整数 start ，finish 和 limit 。
// 同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。
// 如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），
// 且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。
// 请你返回区间 [start..finish] 内强大整数的 总数目 。
// 如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子
// 字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。
// 测试链接 ：https://leetcode.cn/problems/count-the-number-of-powerful-integers/

class Solution 
{
public:
    long long numberOfPowerfulInt1(long long start, long long finish, int limit, string s) 
    {
        string low = to_string(start);
        string high = to_string(finish);
        int n = high.size();
        // 给 low 填充前导零
        low = string(n - low.size(), '0') + low;
        // diff 位后所填写的数字需要和 s 中的数字一样
        int diff = n - s.size();

        long dp[n];
        memset(dp, -1, sizeof dp);
        // 基础版：不考虑前导零
        function<long(int, bool, bool)> f = [&](int i, bool low_limit, bool high_limit) -> long
        {
            if(i == n) return 1;
            if(!low_limit && !high_limit && dp[i] != -1) return dp[i];
            // 第 i 个数位可以从哪枚举到哪
            // 如果对数位有其它约束，应当只在下面的 for 循环做限制
            int down = low_limit ? low[i] - '0' : 0; // 当前数位的下限
            int up = high_limit ? high[i] - '0' : 9; // 当前数位的上限
            long ans = 0;
            if(i < diff)
            {
                for(int d = down; d <= min(up, limit); ++d)
                {
                    ans += f(i + 1, low_limit && d == down, high_limit && d == up);
                }
            }
            else
            {
                // 必须填 s[i - diff]
                int d = s[i - diff] - '0';
                if(d >= down && d <= min(up, limit))
                {
                    ans = f(i + 1, low_limit && d == down, high_limit && d == up);
                }
            }
            if(!low_limit && !high_limit) dp[i] = ans;
            return ans;
        };

        return f(0, true, true);
    }

    long long numberOfPowerfulInt2(long long start, long long finish, int limit, string s) 
    {
        string low = to_string(start);
        string high = to_string(finish);
        int n = high.size();
        // 给 low 填充前导零
        low = string(n - low.size(), '0') + low;
        // diff 位后所填写的数字需要和 s 中的数字一样
        int diff = n - s.size();

        long dp[n];
        memset(dp, -1, sizeof dp);
        // 扩展版：支持前导零
        // is_num：前面是否填了非零数字
        function<long(int, bool, bool, bool)> f = [&](int i, bool low_limit, bool high_limit, bool is_num) -> long
        {
            if(i == n) return is_num;
            if(!low_limit && !high_limit && is_num && dp[i] != -1) return dp[i];
            long ans = 0;
            // 这一位也可以填 0
            if(!is_num && low[i] == '0')
            {
                // 前面填的都是 0, low_limit 一定是 true
                if(i < diff) ans += f(i + 1, true, false, false);
            }
            // 第 i 个数位可以从哪枚举到哪
            // 如果对数位有其它约束，应当只在下面的 for 循环做限制
            int down = low_limit ? low[i] - '0' : 0; // 当前数位的下限
            int up = high_limit ? high[i] - '0' : 9; // 当前数位的上限
            if(i < diff)
            {
                for(int d = max(down, 1 - is_num); d <= min(up, limit); ++d)
                {
                    ans += f(i + 1, low_limit && d == down, high_limit && d == up, true);
                }
            }
            else
            {
                // 必须填 s[i - diff]
                int d = s[i - diff] - '0';
                if(d >= max(down, 1 - is_num) && d <= min(up, limit))
                {
                    ans = f(i + 1, low_limit && d == down, high_limit && d == up, true);
                }
            }
            if(!low_limit && !high_limit && is_num) dp[i] = ans;
            return ans;
        };

        return f(0, true, true, false);
    }
};